#include <iostream>
#include <vector>
#include <UnidirectionLinkedList.hpp>

using namespace std;
class Solution
{
public:
    ListNode *sortList(ListNode *head)
    {
        if (head == nullptr || head->next == nullptr)
        {
            return head;
        }
        vector<ListNode *> levelArray(64);
        ListNode *p = head;
        while (p != nullptr)
        {
            ListNode *next = p->next;
            p->next = nullptr;
            if (levelArray[0] == nullptr)
            {
                levelArray[0] = p;
            }
            else
            {
                recCombine(levelArray, p, 0);
            }
            p = next;
        }
        ListNode *first = nullptr;
        for (int i = 0; i < 64; i++)
        {
            if (levelArray[i] != nullptr)
            {
                if (first == nullptr)
                    first = levelArray[i];
                else
                    first = Combine(levelArray[i], first);
            }
        }
        return first;
    }

    void recCombine(vector<ListNode *> &levelArray, ListNode *node, int index)
    {
        ListNode *newNode = Combine(levelArray[index], node);
        levelArray[index] = nullptr;
        index += 1;
        if (levelArray[index] != nullptr)
            recCombine(levelArray, newNode, index);
        else
            levelArray[index] = newNode;
    }

    ListNode *Combine(ListNode *head1, ListNode *head2)
    {
        if (head1 == nullptr)
        {
            return head2;
        }
        if (head2 == nullptr)
        {
            return head1;
        }
        if (head1->val < head2->val)
        {
            head1->next = Combine(head1->next, head2);
            return head1;
        }
        else
        {
            head2->next = Combine(head1, head2->next);
            return head2;
        }
    }
};

int main()
{
    cout << "Code148" << endl;
    Solution s;
    ListNode *v = CreateLinkedList(vector<int>{4, 2, 1, 3});
    PrintLinkedList(s.sortList(v));
    return 0;
}